#include <bits/stdc++.h>
#include "../../tools/tools.h"
using namespace std;

constexpr int INF = 0x7fffffff; // 无穷大
typedef long long ll;

class Solution {
public:
    int minimumDiameterAfterMerge(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        int d1 = getDiameter(edges1), d2 = getDiameter(edges2);

        return max({d1, d2, (d1 + 1) / 2 + (d2 + 1) / 2});
    }

    // 计算树的最小高度
    int getDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;

        // 构建邻接表
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        int d = 0;
        int dp[n];

        function<void(int, int)> dfs = [&](int u, int fa) {
            for (int v : adj[u]) {
                if (v == fa) continue;
                dfs(v, u);
                d = max(d, dp[u] + dp[v] + 1);
                dp[u] = max(dp[u], dp[v] + 1);
            }
        };
        dfs(1, 0);
        return d;
    }
};
